package niuke;
import java.util.*;
class treenode {
    int val = 0;
    treenode left = null;
    treenode right = null;

    public treenode(int val) {
        this.val = val;

    }
}
    class Node{
        String string;
        int value;
        public Node(int value,String string){
            this.string=string;
            this.value=value;
        }
    }
public class niuKeMain4 {
    public int MoreThanHalfNum_Solution(int[] array) {
        Arrays.sort(array);
        return array[array.length / 2];
    }

    public String[][] topKstrings(String[] strings, int k) {
        // write code here
        HashMap<String, Integer> map = new HashMap<>();
        for (String str : strings) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }
        List<Node> list = new ArrayList<>();
        int count = 0;
        for (Map.Entry<String, Integer> maps : map.entrySet()) {
            list.add(new Node(maps.getValue(), maps.getKey()));
        }
        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.value == o2.value) {
                    return o1.string.compareTo(o2.string);
                }
                return o2.value - o1.value;
            }
        });
        String[][] strings1 = new String[k][2];
        for (int i = 0; i < k; i++) {
            strings1[i][0] = list.get(i).string;
            strings1[i][0] = String.valueOf(list.get(i).value);
        }
        return strings1;
    }

    public String Serialize1(treenode root) {
        if (root==null) {
            return "#";
        }
        StringBuilder str=new StringBuilder();
        Queue<treenode> queue=new LinkedList<>();
        treenode cur=root;
        queue.offer(cur);
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size>0){
                treenode node=queue.poll();
                if (node==null){
                    str.append("#");
                }
                else {
                    str.append(node.val);
                }
                if (node!=null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
                size--;
            }
        }
        return str.toString();
    }
     String Serialize(treenode root) {
         if (root==null) {
             return "#!";
         }
         String str=root.val+"!";
         str+=Serialize(root.left);
         str+=Serialize(root.right);
         return str;
    }
    treenode Deserialize(String str) {
        String[] values=str.split("!");
        Queue<String> queue=new LinkedList<String>();
        for(int i=0;i!=values.length;i++){
            queue.add(values[i]);
        }
        return rec(queue);
    }
    treenode rec(Queue<String> queue){
        String str=queue.poll();
        if (str.equals("#")){
            return null;
        }
        treenode node=new treenode(Integer.parseInt(str));
        node.left=rec(queue);
        node.right=rec(queue);
        return node;
    }
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list=new ArrayList<>();
        if (matrix==null||matrix.length==0){
            return list;
        }
        boolean flag=false;
        int loop=0;
        int row=matrix.length-1,col=matrix[0].length-1;
        if (row==col&&row%2==0){
            flag=true;
        }
        while (row>=loop&&col>=loop){
            for (int i = loop; i <=col; i++) {
                list.add(matrix[loop][i]);
            }
            for (int i = loop; i<=row-1; i++) {
                list.add(matrix[i][col]);
            }
        }
        return list;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();

    }
}
